Binary Search Tree Implementation [O(LogN)]

In computer science, a Binary Tree is a tree data structure in which each Node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set.

Usage:

1. As a means of accessing nodes based on some value or label associated with each node. Binary trees labelled this way are used to implement binary search trees and binary heaps, and are used for efficient searching and sorting. In a normal binary search tree the placement of nodes depends almost entirely on the order in which they were added, and can be re-arranged (for example by balancing) without changing the meaning.

2. As a representation of data with a relevant bifurcating structure. In such cases the particular arrangement of nodes under and/or to the left or right of other nodes is part of the information (that is, changing it would change the meaning). Common examples occur with Huffman coding and cladograms. The everyday division of documents into chapters, sections, paragraphs, and so on is an analogous example with n-ary rather than binary trees.

class TreeNode(object):
    """ Balanced Tree for Binary Search [O(LogN)] """
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insertNode(self, data):
        # data smaller (left child) or greater (right child) of the root data
        # run recurcivelly because the same data structure/rule
        if data < self.data:
            if self.left is None:
                self.left = TreeNode(data)
            else:
                self.left.insertNode(data)
        else:
            if self.right is None:
                self.right = TreeNode(data)
            else:
                self.right.insertNode(data)

    def getMinNode(self):
        if self.left is None:
            return self.data
        else:
            return self.left.getMinNode()

    def getMaxNode(self):
        if self.right is None:
            return self.data
        else:
            return self.right.getMaxNode()

    def removeNode(self, data, parent):
        if data < self.data:
            # continue searh for left child
            if self.left is not None:
                self.left.removeNode(data, self)
        elif data > self.data:
            # continue searh for right child
            if self.right is not None:
                self.right.removeNode(data, self)
        else:
            # parent
            if self.left is not None and self.right is not None:
                # min from greatest leaf
                self.data = self.right.getMinNode()
                self.right.removeNode(data, self)

            elif parent.left == self:
                if self.left is not None:
                    tmpNode = self.left
                else:
                    tmpNode = self.right
                parent.left = tmpNode

            elif parent.right == self:
                if self.right is not None:
                    tmpNode = self.right
                else:
                    tmpNode = self.left
                parent.right = tmpNode

    def traverseInOrderNode(self):
        """ Numerical sorting """
        if self.left is not None:
            # print(self.left.data)
            self.left.traverseInOrderNode()
        print(self.data, end = ', ')
        if self.right is not None:
            # print(self.right.data)
            self.right.traverseInOrderNode()

class BST(object):
    def __init__(self):
        self.root = None

    def insertBST(self, data):
        if not self.root:
            self.root = TreeNode(data)
        else:
            self.root.insertNode(data)

    def removeBST(self, dataToRemove):
        if self.root is not None:
            if self.root.data == dataToRemove:
                tempNode = TreeNode(None)
                tempNode.left = self.root
                self.root.removeNode(dataToRemove, tempNode)
            else:
                self.root.removeNode(dataToRemove, None)

    def getMaxBST(self):
        if self.root is not None:
            return self.root.getMaxNode()

    def getMinBST(self):
        if self.root is not None:
            return self.root.getMinNode()

    def traverseInOrderBST(self):
        if self.root is not None:
            self.root.traverseInOrderNode()

bst = BST()
bst.insertBST(12)
bst.insertBST(10)
bst.insertBST(-2)
bst.insertBST(1)
bst.traverseInOrderBST()
print()

bst.removeBST(10)
bst.traverseInOrderBST()
print()

bst.removeBST(1)
bst.traverseInOrderBST()
print()

bst.removeBST(-2)
bst.traverseInOrderBST()
print()

-2, 1, 10, 12,
-2, 1, 12,
-2, 12,
12,

bst = BST()
bst.insertBST(12)
bst.insertBST(10)
bst.insertBST(-2)
bst.insertBST(1)

assert bst.getMaxBST() == 12
assert bst.getMinBST() == -2

# Unbalanced BST - not efficient -> this is a Linked List (O(N), not O(LogN))
bst = BST()
bst.insertBST(1)
bst.insertBST(2)
bst.insertBST(3)
bst.insertBST(4)